package leetcode.f1t100;

import leetcode.struct.ListNode;

import java.util.Stack;

/**
 * 从链表中删除倒数第N个元素
 * https://leetcode.com/problems/remove-nth-node-from-end-of-list/
 *
 * @Author lichongxiao
 * @Date 2022/9/30 9:17
 */
public class Q19_RemoveNthNodeFromEndOfList {

    public static void main(String[] args) {
        new Q19_RemoveNthNodeFromEndOfList().test();
    }

    public void test(){
        ListNode head = new ListNode(1, new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5,null)))));
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
//        head = removeNthFromEnd(head,5);
        head = removeNthFormEndOnePass(head,2);

        cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null){
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        if(n > stack.size()){
            return head;
        }
        if(n == stack.size()){
            return head.next;
        }
        while(n > 0) {
            cur = stack.pop();
            n--;
        }
        stack.peek().next = cur.next;
        return head;
    }

    public ListNode removeNthFormEndOnePass(ListNode head, int n) {
        ListNode fast = head,slow = head;
        while(n > 0){
            fast = fast.next;
            n--;
        }
        if(fast == null){
            return head.next;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}
